1. Field of the Invention
The present invention relates to a priority determining circuit of an associative memory and more particularly, to a priority determining circuit of an associative memory for use in a data processing circuit in which, in response to coincidence of stored data in an associative memory with externally applied retrieval data, coincidence signals from an address of the coinciding stored data are sequentially selected and provided according to predetermined priority levels and the selected and provided coincidence signal is converted into a predetermined address code.
2. Description of the Background Art
FIG. 3 is a block diagram showing a conventional example including a peripheral circuit portion for reading desired data stored in an associative memory. Referring to FIG. 3, associative memory 1 has a storage capacity of n words (1 word is m bits), that is, n.times.m bits. In order to retrieve data stored in associative memory 1, retrieval data having a word length of m bits is applied externally to associative memory 1 through a latch circuit 2. The retrieval data is compared with all n pieces of data stored in associative memory 1. If data coinciding with the retrieval data exists, a coincidence signal is provided from an address corresponding to a word position where the coinciding data is stored and is applied to a priority determining circuit 4 through a latch circuit 3.
Because of the characteristics of associative memory 1, plural pieces of data coinciding with the retrieval data sometimes exist in associative memory 1. In this case, a plurality of coincidence signals are provided simultaneously from associative memory 1. It is difficult to process these signals simultaneously in parallel, so that priority determining circuit 4 selects from these coincidence signals and outputs the one(s) having the highest priority.
The coincidence signal selected by priority determining circuit 4 is applied to an encoder 5 at a succeeding stage, converted into a predetermined address code (for example, a binary digit) which is then transmitted to decoder 6. Decoder 6 decodes the address code and designates one particular address for reading data from associative memory 1, so that data coinciding with the retrieval data (m bit) among data stored in associative memory 1 is read.
FIG. 4 is a specific block diagram of the priority determining circuit and the encoder shown in FIG. 3. Referring to FIG. 4, priority determining circuit 4 includes contention arbitrating circuit 41 and signal selecting circuit 42. Contention arbitrating circuit 41 receives coincidence signals M1-M8 (in an example shown in FIG. 4, the number of words is 8) applied from latch circuit 3 shown in FIG. 3 and outputs inhibiting signals I1-I8.
Contention arbitrating circuit 41 includes P channel MOS transistors P1-P8 and N channel MOS transistors N10, N21, N32, N43, N54, N65, N76 and N87. P channel MOS transistors P1-P8 are connected in series. A coincidence signal Mj (1.ltoreq.j.ltoreq.8) is applied to each of the gates. A block inhibiting signal INH is applied to the drain of P channel MOS transistor P8, and a block coincidence signal HIT is provided from the source of P channel MOS transistor P1. The drain of each of P channel MOS transistors P1-P8 is connected to one terminal of each of AND gates AND1-AND8, respectively, included in signal selecting circuit 42. Each of coincidence signals M1-M8 is applied to the other input terminal of each of AND gates AND1-AND8, respectively.
Block inhibiting signal INH is a signal activating all inhibiting signals I1-I8 and is applied to the drain of P channel MOS transistor P8. Block coincidence signal HIT indicates at least one coincidence signal is in an active state.
In the contention arbitrating circuit 41 shown in FIG. 4, when coincidence signal M4 is in an active state, (an "H" level), N channel MOS transistor N43 is rendered conductive, and consequently inhibiting signal I3 whose priority level is lower by one is activated. Consequently, even if the coincidence signal M3 attains "H" level, for example, the output of an AND gate AND 3 would be at "L" level. If coincidence signal M4 is in an inactive state ("L" level), P channel MOS transistor P4 is rendered conductive, and its own inhibiting signal I4 is propagated as an inhibiting signal I3 whose priority level is lower by one. If the coincidence signal M1 is active, N channel MOS transistor N10 is rendered conductive, and consequently, block coincidence signal HIT is activated to "L" level. However, if the coincidence signal M1 is at an inactive state, P channel MOS transistor P1 is rendered conductive, and inhibiting signal I1 is propagated as the block coincidence signal HIT. Such method of reducing delay time by inhibiting, by the gate circuit, output of the lower signal in response to the coincidence signal is disclosed in, for example, "Content-Addressable Memories" (Springer Series in Information Sciences) by Teuvo Kohnen and in "An Integrated Content Addressable Memory System" by John Patrick Wade.
Signal selecting circuit 42 receives inhibiting signals I1-I8 and outputs arbitration signals T1-T8. Signal selecting circuit 42 inhibits or allows output of coincidence signals M1-M8 as arbitration signals T1-T8, depending on states of inhibiting signals I1-I8, respectively. As a result, only one of arbitration signals T1-T8 is in an active state.
Encoder 5 includes three 4 -input OR circuits, receives arbitration signals T1-T8 provided from signal selecting circuit 42 and outputs encoding signals F0-F2. Encoder 5 converts coincidence information from associative memory 1 into an address code of binary number. In the example shown in FIG. 4, the number of word is 2.sup.3, so that an output of 3 bits can be obtained.
FIG. 5 is a block diagram showing another example of the encoding circuit. The contention arbitrating circuit 43 of the encoding circuit 4a shown in FIG. 5 receives coincidence signals M1 to M8 by using OR gates OR1 to OR8 and outputs inhibiting signals I1 to I8. More specifically, when coincidence signal M4 is activated to "H" level, for example, the output of the OR gate OR5, that is, the inhibiting signal I3 attains an "L" level, so that the AND gate AND3 whose priority level is lower by one is closed and the output of AND3 is at an "L" level. Therefore, even if the coincidence signal M3 attains to an "H" level, the arbitrating signal T3 output from AND gate AND3 attains an "L" level.
In a conventional priority determining circuit 4 shown in FIG. 4, block inhibiting signal INH is propagated through P channel MOS transistors P8-P1 connected in series. Therefore, it takes some time for arbitration signals T1-T8 to attain given values after coincidence signal Mj is applied to priority determining circuit 41. In the example shown in FIG. 4, when coincidence signal M8 is in an active state and the rest of coincidence signals M1-M7 are all in an inactive state, inhibiting signal should be propagated sequentially from P channel MOS transistor P7 to a succeeding lower side. If the number of word is n, the signal should pass one N channel MOS transistor and n-1 P channel MOS transistors until block coincidence signal HIT is activated, that is, according to the embodiment shown in FIG. 4, the signal should pass one N channel MOS transistor and seven P channel MOS transistors. If the number of words in associative memory 1 is small, such delay in propagation is not a serious problem. However, since the capacity of the associative memory has been increased and the delay time of propagation becomes longer, there arises a problem that it takes long to determine priority.